package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
//n皇后问题
public class Pra6 {
    
    class Backtrack {
        //回溯解法
        public boolean check(int[] queen, int i, int j) {
            // (i, j)位置放置皇后是否合法
            //i不必检查
            for (int k = 0; k < i; k++) {
                //在同一个竖线或者斜线上
                if (queen[k] == j || Math.abs(i - k) == Math.abs(queen[k] - j)) {
                    return false;
                }
            }
            return true;
        }
        List<List<String>> res = new ArrayList<>();
        public void recur(int idx, int[] queen) {
            int n = queen.length;
            if (idx == n) {
                //抵达终点
                List<String> list = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    StringBuilder sb = new StringBuilder();
                    for (int j = 0; j < n; j++) {
                        if (j == queen[i]) {
                            sb.append("Q");
                        } else {
                            sb.append("*");
                        }
                    }
                    list.add(sb.toString());
                }
                res.add(list);
                return;
            }
            for (int i = 0; i < n; i++) {
                if (check(queen, idx, i)) {
                    queen[idx] = i; //会自己被覆盖
                    recur(idx + 1, queen);
                    queen[idx] = 0;
                }
            }
        }

        public List<List<String>> nQueue(int n) {
            recur(0, new int[n]);
            return res;
        }
    }

    @Test
    public void test() {
        int[] nums = new int[]{};
        Backtrack bt = new Backtrack();
        System.out.println(bt.nQueue(6));
    }
}
